-- Assignment 2
-- 
-- We want to test the following things:
-- * the basics: are our assumptions about the used test data correct
-- * all nodes/letters in the graph should be included in the shortest path
-- * the found path has to be shorter than the most inefficient path, which
--   is the factorial of the number of nodes
-- * (TODO) the found path has to be shorter than all other valid paths
--
-- Indication of time spent: 7 man hours

module TestPrim where

import Data.List
import Unsafe.Coerce
import Test.QuickCheck
import Prim

-- Replacing newtype with data results in a segmentation fault. How come?
newtype Edge = Edge (Char, Char, Int)

main :: IO ()
main = do
  quickCheck prop_basics
  quickCheck prop_allNodesPresent
  quickCheck prop_testShorterThanWorstPath
  quickCheck prop_primIsShortest

prop_basics :: Edge -> Bool
prop_basics edge = (fromNode edge) >= 'A' && (fromNode edge) <= 'H' &&
                   (toNode edge) >= 'A' && (toNode edge) <= 'H' &&
                   (weight edge) > 0 && (weight edge) <= 10
                   
prop_allNodesPresent :: [Edge] -> Bool
prop_allNodesPresent edges = numNodes (primToEdges edges) == numNodes edges

prop_testShorterThanWorstPath :: [Edge] -> Bool
prop_testShorterThanWorstPath edges = length (primToEdges edges) < factorial (length edges)

prop_primIsShortest :: [Edge] -> Bool
-- TODO Check if the prim path is shorter than all other paths
prop_primIsShortest edges = pathLength (primToEdges edges) < 100

instance Arbitrary Edge where
  arbitrary = do from <- elements ['A'..'H']
                 to <- elements [x | x <- ['A'..'H'], x /= from]
                 val <- elements [1..10]
                 return (Edge (from, to, val))
                 
instance Show Edge where
  show (Edge (x, y, z)) = " " ++ show x ++ " -> " ++ show y ++ " (" ++ show z ++ ") "

fromNode :: Edge -> Char
fromNode (Edge (x, y, z)) = x

toNode :: Edge -> Char
toNode (Edge (x, y, z)) = y

weight :: Edge -> Int
weight (Edge (x, y, z)) = z

getNodesIn :: [Edge] -> [Char]
getNodesIn edges = nub ([fromNode x | x <- edges] ++ [toNode x | x <- edges])

numNodes :: [Edge] -> Int
numNodes edges = length (getNodesIn edges)

pathLength :: [Edge] -> Int
pathLength [] = 0
pathLength edges = weight (head edges) + pathLength (tail edges)

factorial :: Int -> Int
factorial 0 = 1
factorial x = x * (factorial (x - 1))

-- This function only exists because Haskell doesn't seem to detect that Edge
-- is already an alias of (Char, Char, Int).
toTuples :: [Edge] -> [(Char, Char, Int)]
toTuples edges = [toTuple x | x <- edges]
  where
    toTuple :: Edge -> (Char, Char, Int)
    toTuple (Edge (x, y, z)) = (x, y, z)

-- Prim.hs defines edges as a generic (a, a, b), which we need to cast to our
-- own type. This is obviously not a very safe way to cast, but as far as we
-- know there aren't any alternatives in this particular case.
primToEdges :: [Edge] -> [Edge]
primToEdges edges = gensToEdges (prim (toTuples edges))
  where
    gensToEdges :: [(a, a, b)] -> [Edge]
    gensToEdges gens = [genToEdge x | x <- gens]
      where
        genToEdge :: (a, a, b) -> Edge
        genToEdge gen = unsafeCoerce gen
